package main

type ListNode struct {
	Val  int
	Next *ListNode
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func sortedListToBST(head *ListNode) *TreeNode {
	return buildTree(head, nil)
}

func buildTree(head *ListNode, tail *ListNode) *TreeNode {
	if head == tail {
		return nil
	}
	fast := head
	slow := head
	for fast != tail && fast.Next != tail {
		fast = fast.Next.Next
		slow = slow.Next
	}
	root := &TreeNode{Val: slow.Val}
	root.Left = buildTree(head, slow)
	root.Right = buildTree(slow.Next, tail)
	return root
}

func main() {
	list := &ListNode{
		Val: -10,
		Next: &ListNode{
			Val: -3,
			Next: &ListNode{
				Val: 0,
				Next: &ListNode{
					Val: 5,
					Next: &ListNode{
						Val: 9,
					},
				},
			},
		},
	}
	root := sortedListToBST(list)
	println(root)
}
